package com.bo.day20241014;

/**
 * 在线测试链接 : https://leetcode.com/problems/largest-bst-subtree
 * 描述 : 给定一个二叉树的头节点head，返回这颗二叉树中最大的二叉搜索子树的大小
 * 思路：
 * 1.经过head节点，说明本身就是一个搜索二叉树
 * 2.不经过head节点，左右子树比较
 *
 * @Author: gpb
 * @Date: 2024/10/15 14:50
 * @Description:
 */
public class MaxSubBSTSize {

    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode (int value) {
            val = value;
        }
    }

    // 定义Info信息
    public static class Info {
        // 左子树最大值
        public int max;
        // 右子树最小值
        public int min;
        // 搜索二叉树最大节点数
        public int maxBSTSubtreeSize;
        // 所有节点，当allSize==maxBSTSubtreeSize，则肯定是一个搜索二叉树
        public int allSize;

        public Info (int max, int min, int maxBSTSubtreeSize, int allSize) {
            this.max = max;
            this.min = min;
            this.maxBSTSubtreeSize = maxBSTSubtreeSize;
            this.allSize = allSize;
        }
    }

    public static int largestBSTSubtree (TreeNode head) {
        if (head == null) {
            return 0;
        }
        return process(head).maxBSTSubtreeSize;
    }

    public static Info process (TreeNode head) {
        // 子节点不好出处理返回null
        if (head == null) {
            return null;
        }
        // 左右子树信息
        Info leftInfo = process(head.left);
        Info rightInfo = process(head.right);
        // 最大值和最小值默认为当前节点值
        int max = head.val;
        int min = head.val;
        // 初始化所有节点数量
        int allSize = 1;
        // 左子树不为空，则更新最大值和最小值，节点数量
        if (leftInfo != null) {
            max = Math.max(max, leftInfo.max);
            min = Math.min(min, leftInfo.min);
            allSize += leftInfo.allSize;
        }
        if (rightInfo != null) {
            max = Math.max(max, rightInfo.max);
            min = Math.min(min, rightInfo.min);
            allSize += rightInfo.allSize;
        }
        // 计算出最大节点数
        // p1情况，左树不为空，获取到左树的最大搜索二叉树的节点数
        int p1 = -1;
        if (leftInfo != null) {
            p1 = leftInfo.maxBSTSubtreeSize;
        }
        // p2情况，右树不为空，获取到右树的最大搜索二叉树的节点数
        int p2 = -1;
        if (rightInfo != null) {
            p2 = rightInfo.maxBSTSubtreeSize;
        }
        // p3情况：左右子树都是搜索二叉树，则当前节点为搜索二叉树的头节点，返回当前节点的节点数
        int p3 = -1;
        // 判断左子树是否为搜索二叉树，左子树为空默认为搜索二叉树，如果不为空，左子树的最大搜索二叉树节点数量和左子树节点数量相等(可能是搜索二叉树)，如果不相等说明肯定不是搜索二叉树
        boolean leftBST = leftInfo == null ? true : (leftInfo.maxBSTSubtreeSize == leftInfo.allSize);
        // 判断右子树是否为搜索二叉树，右子树为空默认为搜索二叉树，如果不为空，右子树的最大搜索二叉树节点数量和左子树节点数量相等(可能是搜索二叉树)，如果不相等说明肯定不是搜索二叉树
        boolean rightBST = rightInfo == null ? true : (rightInfo.maxBSTSubtreeSize == rightInfo.allSize);
        // 判断是否是搜索二叉树
        if (leftBST && rightBST) {
            // 上面那层校验说明可能是搜索二叉树
            // 再次校验左树最大值<当前节点，右树最小值>当前节点，则说明是搜索二叉树，返回当前节点的节点数
            boolean leftMaxLessCurrent = leftInfo == null ? true : (leftInfo.max < head.val);
            // 再次校验右树最小值>当前节点，则说明是搜索二叉树，返回当前节点的节点数
            boolean rightMinMoreCurrent = rightInfo == null ? true : (rightInfo.min > head.val);
            // leftMaxLessCurrent和rightMinMoreCurrent都成立说明是搜索二叉树
            if (leftMaxLessCurrent && rightMinMoreCurrent) {
                // p3: 左子树最大节点数+右子树最大节点数+当前节点
                int leftAllSize = leftInfo == null ? 0 : leftInfo.allSize;
                int rightAllSize = rightInfo == null ? 0 : rightInfo.allSize;
                p3 = leftAllSize + rightAllSize + 1;
            }
        }
        return new Info(max, min, Math.max(p3, Math.max(p1, p2)), allSize);
    }
}
